What is metropolis algorithm?

The Metropolis algorithm is a Markov chain Monte Carlo (MCMC) method used to sample from complex probability distributions. It was developed by N. Metropolis and S. Ulam in the late 1940s and early 1950s.

The algorithm is used to generate sequences of samples from a specified probability distribution, which can be very useful in many fields, such as statistics, physics, and computer science.

The Metropolis algorithm works by iteratively proposing new candidate points in the sample space and then accepting or rejecting them based on a certain criterion. The acceptance/rejection decision is based on the ratio of the candidate point's probability density to the current point's probability density.

The key advantage of the Metropolis algorithm is that it can be used to sample from very high-dimensional probability distributions, where other methods may be computationally infeasible.

The Metropolis algorithm is widely used in applications such as Bayesian statistics, statistical physics, and machine learning. It has been extended and adapted into more sophisticated algorithms, such as the Gibbs sampler and Hamiltonian Monte Carlo.